package stir.cs.succ;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

import javax.swing.JButton;
import javax.swing.JFileChooser;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextArea;
import javax.swing.JTextField;

import succ.stirnav.map.Map;
import succ.stirnav.map.Point;

public class Search implements ActionListener {

	// declare core variables

	private Map map;
	private List<Point> complete, open, closed;
	private List<String> instructions;
	private List<List<Point>> completeNeighbours;
	private Point current;
	private boolean targetFound, neighbourFound, startFound;
	private String path, filepath, root;
	private final double H;
	// declare new Comparator
	private Comparator<Point> comp = new Comparator<Point>() {
		@Override
		public int compare(Point o1, Point o2) {
			if(o1.getFScore() < o2.getFScore()) return -1;
			if(o1.getFScore() > o2.getFScore()) return 1;
			return 0;
		}
	};

	// declare gui elements

	private JFrame frame, contents;
	private JPanel pane, contentsPane;
	private Dimension paneDim, cPD;
	private JTextField loc, dest;
	private JTextArea route;
	private JLabel locl, destl, routel;
	private JButton search;
	private JFileChooser fc = new JFileChooser();

	public Search() {
		// get map file to use
		int returnVal = fc.showOpenDialog(frame);
		if(returnVal == JFileChooser.APPROVE_OPTION) {
			filepath = fc.getSelectedFile().getAbsolutePath();
		}
		// initiate core variables
		try {
			this.map = Map.loadMap(filepath);
		}
		catch (NullPointerException npe) {
			System.err.println("File not found.");
			System.exit(1);
		}
		this.complete = map.getPoints();
		this.open = new LinkedList<Point>();
		this.closed = new LinkedList<Point>();
		this.completeNeighbours = new LinkedList<List<Point>>();
		this.instructions = new LinkedList<String>();
		this.populateNeighbours();
		this.targetFound = false;
		this.neighbourFound = false;
		this.startFound = false;
		this.H = 0.25;
		this.path = "     ";
		// initiate gui variable
		this.paneDim = new Dimension(840,480);
		this.cPD = new Dimension(530, 860);
	}

	private void populateNeighbours() {
		for(int i = 0; i < complete.size(); i++) {
			List<Integer> tmp = complete.get(i).getNeighbours();
			List<Point> neighbours = new LinkedList<Point>();
			for(int j = 0; j < tmp.size(); j++) {
				neighbours.add(complete.get(findByID(tmp.get(j), complete)));
			}
			completeNeighbours.add(neighbours);
		}
	}

	private void createGUI() {
		// contents window gui
		this.contents = new JFrame();
		this.contents.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		this.contents.setTitle("Contents");
		this.contents.setLocation(900,0);
		this.contents.setSize(570,900);
		this.contents.setBackground(Color.black);
		this.contents.setLayout(new FlowLayout());

		this.contentsPane = new JPanel();
		this.contentsPane.setPreferredSize(cPD);
		this.contentsPane.setBackground(Color.white);
		this.contents.add(contentsPane);

		this.contents.setVisible(true);

		// main window gui
		this.frame = new JFrame();
		this.frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		this.frame.setTitle("StirNav v0.1 [BETA] Java Implementation");
		this.frame.setSize(880,900);
		this.frame.setBackground(Color.black);
		this.frame.setLayout(new FlowLayout());

		this.pane = new JPanel();
		this.pane.setPreferredSize(paneDim);
		this.pane.setBackground(Color.white);
		this.frame.add(pane);

		this.locl = new JLabel("Enter Location:");
		this.frame.add(locl);

		this.loc = new JTextField();
		this.loc.setColumns(22);
		this.frame.add(loc);

		this.destl = new JLabel("Enter Destination:");
		this.frame.add(destl);

		this.dest = new JTextField();
		this.dest.setColumns(22);
		this.frame.add(dest);

		this.search = new JButton("Find Route");
		this.search.addActionListener(this);
		this.frame.add(search);

		this.routel = new JLabel("Route:");
		this.frame.add(routel);

		this.route = new JTextArea();
		this.route.setColumns(60);
		this.route.setRows(15);
		this.route.setLineWrap(true);
		this.route.setWrapStyleWord(true);
		this.frame.add(route);

		this.frame.setVisible(true);

		while(true) {
			this.route.setText(path);
			this.drawMap();
			this.drawContents();
		}
	}

	private void drawMap() {
		// draw edges
		Graphics g = pane.getGraphics();
		for(int i = 0; i < complete.size(); i++) {
			// draw edges
			g.setColor(Color.black);
			for(int j = 0; j < completeNeighbours.get(i).size(); j++) {
				g.drawLine(complete.get(i).getPosition().getX(), complete.get(i).getPosition().getY(), completeNeighbours.get(i).get(j).getPosition().getX(), completeNeighbours.get(i).get(j).getPosition().getY());
			}
			// draw points
			g.setColor(Color.blue);
			g.fillOval(complete.get(i).getPosition().getX()-3, complete.get(i).getPosition().getY()-3, 6, 6);
			// circle points
			g.setColor(Color.red);
			g.drawOval(complete.get(i).getPosition().getX()-5, complete.get(i).getPosition().getY()-5, 10, 10);
			// label with ids
			g.setColor(Color.black);
			g.drawString(Integer.toString(complete.get(i).getID()), complete.get(i).getPosition().getX(), complete.get(i).getPosition().getY());
		}
	}

	private void drawContents() {
		Graphics cg = contentsPane.getGraphics();
		cg.setColor(Color.black);
		cg.drawString("ID:  Name", 10, 12);
		cg.drawString("ID:  Name", 150, 12);
		cg.drawString("ID:  Name", 290, 12);
		int highY = 0;
		for(int i = 0; i < complete.size(); i++) {
			if(i < complete.size()/3) {
				cg.drawString(complete.get(i).getID() + ":   " + complete.get(i).getName(), 10, (i*12)+36);
			}
			else {
				if(i < (complete.size()/3)*2) {
					cg.drawString(complete.get(i).getID() + ":   " + complete.get(i).getName(), 150, (i*12)-((complete.size()/3)*12)+36);
				}
				else {
					cg.drawString(complete.get(i).getID() + ":   " + complete.get(i).getName(), 290, (i*12)-(((complete.size()/3)*2)*12)+36);
					highY = (i*12)-(((complete.size()/3)*2)*12)+36;
				}
			}
		}
		if(highY < 520) {
			cg.drawString("The list above shows the corresponding room names to the IDs labelled on the ", 10, 532);
			cg.drawString("map.\n Note that this implementation is not robust and so will not accept ", 10, 544);
			cg.drawString("invalid room names. This was felt to be acceptable as in the final Android ", 10, 556);
			cg.drawString("application the selection will be made from a list. Names are not case sensitive.", 10, 568);
		}
	}

	private int findByID(int id, List<Point> list) {
		int index = 0;
		for (int i = 0; i < list.size(); i++) {
			if(list.get(i).getID() == id) {
				index = i;
				break;
			}
		}
		return index;
	}

	private int findByName(String name, List<Point> list) {
		int index = 0;
		for (int i = 0; i < list.size(); i++) {
			if(list.get(i).getName().equals(name.toUpperCase())) {
				index = i;
				break;
			}
		}
		return index;
	}

	@Override
	public void actionPerformed(ActionEvent e) {
		this.resetPath();
		this.resetStates();
		if(e.getSource() == search) {
			this.root = this.loc.getText().toUpperCase();
			this.findRoute(this.loc.getText().toUpperCase(), this.dest.getText().toUpperCase());
		}
		this.resetDisplay();
	}

	private void findRoute(String start, String end) {
		// base case
		// either path found: ie. start = end
		// or 
		// open list exhausted, closed list not empty (ie. nodes have been considered) and start = null
		if(start.equals(end)) {
			targetFound = true;
			closed.add(open.get(findByName(start, open)));
		}
		if(open.isEmpty() && !closed.isEmpty()) {
			instructions.add("No path exists");
			displayResult(instructions);
		}
		// if neither base case satisfied, then run recursion
		if(!targetFound) {
			// check if start node already in open list
			for(int h = 0; h < open.size(); h++) {
				if(open.get(h).getID() == complete.get(findByName(start, complete)).getID()) {
					startFound = true;
					break;
				}
			}
			// add starting node to open list if not already present
			if(!startFound) {
				open.add(complete.get(findByName(start, complete)));
			}
			// set and examine f scores of each node in the open list, set node with lowest f score to current node
			// open list will initially consist only of original root node, so will always default to selecting this node on first run
			for(int i = 0; i < open.size(); i++) {
				// set each open node's f score
				open.get(i).setFScore(calcGScore(open.get(i)) + calcHScore(open.get(i), end));
			}
			int lowestInOpen = 0;
			for(int j = lowestInOpen + 1; j < open.size(); j++) {
				// Selecting node with lowest f score from open list
				if(open.get(j).getFScore() < open.get(lowestInOpen).getFScore()) {
					lowestInOpen = j;
				}
			}
			// set current node to be node with lowest f score based on starting position
			current = open.get(lowestInOpen);
			// reset lowest in open
			lowestInOpen = 0;
			// remove current node from open list, place on closed list
			closed.add(open.get(findByID(current.getID(), open)));
			open.remove(open.get(findByID(current.getID(), open)));
			// for each node adjacent to the current node do the following
			// compile list of neighbouring nodes
			List<Point> neighbours = new LinkedList<Point>();
			for(int k = 0; k < current.getNeighbours().size(); k++) {
				neighbours.add(complete.get(findByID(current.getNeighbours().get(k), complete)));
			}
			// check if any neighbours are already on the closed list (ie. have already been considered)
			// for each neighbour of current point
			for(int l = 0; l < neighbours.size(); l++) {
				// compare against each member of the closed list
				for(int m = 0; m < closed.size(); m++) {
					// if a matching ID is found for a neighbour on the closed list
					if(closed.get(m).getID() == neighbours.get(l).getID()) {
						// remove that neighbour from the list, causing all other list members to be 'moved' one position to the left
						neighbours.remove(l);
						// decrement l so the neighbour now at the position just considered isn't skipped over
						l--;
						break;
					}
				}
			}
			// for each remaining neighbour 
			for(int m = 0; m < neighbours.size(); m++) {
				// compare against each member of the open list
				for(int n = 0; n < open.size(); n++) {
					// if a matching ID is found for a neighbour in the open list
					if(open.get(n).getID() == neighbours.get(m).getID()) {
						// set duplicate boolean to true
						neighbourFound = true;
						break;
					}
				}
				// if neighbour has not been matched to a member of the open list
				if(!neighbourFound) {
					// set current node to be neighbour's parent
					neighbours.get(m).setParent(current);
					// set neighbours F, G & H scores
					neighbours.get(m).setGScore(calcGScore(neighbours.get(m)));
					neighbours.get(m).setHScore(calcHScore(neighbours.get(m), end));
					neighbours.get(m).setFScore(neighbours.get(m).getGScore() + neighbours.get(m).getHScore());
					// add the neighbour to the open list
					open.add(neighbours.get(m));
				}
				else {
					// if neighbour already in open list, work out if shorter route obtained by going via current point and any
					// predecessors back to parent of neighbour being considered
					double altGScore = 0;
					Point tmp = current;
					while(tmp.getParent().getID() != open.get(findByID(neighbours.get(m).getID(), open)).getParent().getID()) {
						altGScore = altGScore + tmp.getGScore();
						// check if alt g score > curr g score, if it is then no point continuing
						if(altGScore > open.get(findByID(neighbours.get(m).getID(), open)).getGScore()) {
							break;
						}
						tmp = tmp.getParent();
					}
					altGScore = altGScore + tmp.getGScore();
					// if altGScore shorter than G score currently assigned to neighbour when it was originally added to open list
					if(altGScore < open.get(findByID(neighbours.get(m).getID(), open)).getGScore()) {
						// set neighbour's new parent to be current node
						open.get(findByID(neighbours.get(m).getID(), open)).setParent(current);
						open.get(findByID(neighbours.get(m).getID(), open)).setGScore(calcGScore(open.get(findByID(neighbours.get(m).getID(), open))));
					}
				}
				// set neighbourFound trigger to false for next neighbour
				neighbourFound = false;
			}
			// clear neighbours list for next recursion
			neighbours.clear();
			// sort open list by f score so as to try best node next
			// sort using previously declared comparator
			Collections.sort(open, comp);
			findRoute(open.get(0).getName(), end);
		}
		else {
			displayResult(compileRoute(convertClosed(root, closed)));
		}
	}

	private double calcGScore(Point p) {
		if(p.getParent() != null) {
			// sets g score where point p has a parent
			double diffX = p.getParent().getPosition().getX() - p.getPosition().getX();
			double diffY = p.getParent().getPosition().getY() - p.getPosition().getY();
			p.setGScore(Math.sqrt((diffX*diffX)+(diffY*diffY)));
		}
		else {
			// sets g score where point p has no parent (ie. is original starting node)
			// g score in this case will always be 0 as root is 0 units of distance away from itself
			p.setGScore(0);
		}
		return p.getGScore();
	}

	private double calcHScore(Point p, String destination) {
		double diffX = complete.get(findByName(destination, complete)).getPosition().getX() - p.getPosition().getX();
		double diffY = complete.get(findByName(destination, complete)).getPosition().getY() - p.getPosition().getY();
		p.setHScore(H*(Math.sqrt((diffX*diffX)+(diffY*diffY))));
		return p.getHScore();
	}

	private List<Point> convertClosed(String root, List<Point> cl) {
		// assemble route in reverse order by taking parent of each node back to original root node	
		List<Point> reverseOrder = new LinkedList<Point>();
		reverseOrder.add(cl.get(cl.size()-1));
		int counter = 0;
		while(!(reverseOrder.get(counter).getParent().getName().equals(root))) {
			reverseOrder.add(reverseOrder.get(counter).getParent());
			counter++;
		}
		reverseOrder.add(reverseOrder.get(reverseOrder.size()-1).getParent());
		// reassemble route in correct order for display purposes
		List<Point> rt = new LinkedList<Point>();
		while(reverseOrder.size() > 0) {
			rt.add(reverseOrder.get(reverseOrder.size()-1));
			reverseOrder.remove(reverseOrder.size()-1);
		}
		return rt;
	}

	private List<String> compileRoute(List<Point> route) {
		instructions.add(" " + 1 + ". Progress from " + route.get(0).getName() + " to " + route.get(1).getName() + ".");

		for(int i = 1; i < route.size()-1; i++) {			
			if (i%4 == 0) {
				// check if current node is stairs
				if((route.get(i).getType() == 1 || route.get(i).getType() == 7) && (route.get(i+1).getType() == 1 || route.get(i+1).getType() == 7)) {
					int curFloor = -1, destFloor = -1;
					curFloor = Integer.parseInt(route.get(i).getName().substring(0,1));
					destFloor = Integer.parseInt(route.get(i+1).getName().substring(0,1));
					if (route.get(i).getType() == 1) {
						if (curFloor > destFloor) {
							instructions.add(" " + (i+1) + ". Go down the stairs to floor " + destFloor + ".\n");
						}
						else {
							instructions.add(" " + (i+1) + ". Go up the stairs to floor " + destFloor + ".\n");
						}
					}
					else {
						if (curFloor > destFloor) {
							instructions.add(" " + (i+1) + ". Take the elevator down to floor " + destFloor + ".\n");
						}
						else {
							instructions.add(" " + (i+1) + ". Take the elevator up to floor " + destFloor + ".\n");
						}
					}
				} 
				else {
					if((route.get(i-1).getType() == 1 || route.get(i-1).getType() == 7) && (route.get(i).getType() == 1 || route.get(i).getType() == 7)) {
						instructions.add(" " + (i+1) + ". Progress from " + route.get(i).getName() + " to " + route.get(i+1).getName() + ".\n");
					}
					else {
						// if previous move more of a horizontal change then
						if(Math.pow(route.get(i).getPosition().getX() - route.get(i-1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i-1).getPosition().getY(), 2)) {
							// if previous move was to the left then
							if(route.get(i).getPosition().getX() - route.get(i-1).getPosition().getX() < 0) {
								// if next move more of a horizontal change then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move back to the right
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself from " + route.get(i).getName() + " and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move also to the left
									else {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + "  towards " + route.get(i+1).getName() + ".\n");
									}
								}
								// else if next move more of a vertical change then
								else {
									// if next move down
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// else if next move up
									else {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
							}
							// else if previous move was to the right then
							else {
								// if next move is more horizontal than vertical then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move is also to the right then
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + " towards " + route.get(i+1).getName() + ".\n");
									}
									// if next move is to the left
									else {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself from " + route.get(i).getName() + " and go to " + route.get(i+1).getName() + ".\n");
									}
								}
								// if next move is more vertical than horizontal then
								else {
									// if next move is down
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is up
									else {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
							}
						}
						// else if last move was more vertical than horizontal then 
						else {
							// if last move was up then
							if(route.get(i).getPosition().getY() - route.get(i-1).getPosition().getY() < 0) {
								// if next move is more horizontal than vertical then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move is to the right then
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is to the left then
									else {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
								// if next move is more vertical than horizontal then
								else {
									// if next move is down then
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is up
									else {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + " towards " + route.get(i+1).getName() + ".\n");
									}
								}
							}
							// if last move was down then
							else {
								// if next move is more horizontal than vertical then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move is to the right then
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is to the left then
									else {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + " and go to " + route.get(i+1).getName() + ".\n");
									}
								}
								// if next move is more vertical than horizontal then
								else {
									// if next move is down then
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + " towards " + route.get(i+1).getName() + ".\n");
									}
									// if next move is up
									else {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
							}
						}
					}
				}
			}
			else {
				// check if current node is stairs
				if((route.get(i).getType() == 1 || route.get(i).getType() == 7) && (route.get(i+1).getType() == 1 || route.get(i+1).getType() == 7)) {
					int curFloor = -1, destFloor = -1;
					curFloor = Integer.parseInt(route.get(i).getName().substring(0,1));
					destFloor = Integer.parseInt(route.get(i+1).getName().substring(0,1));
					if (route.get(i).getType() == 1) {
						if (curFloor > destFloor) {
							instructions.add(" " + (i+1) + ". Go down the stairs to floor " + destFloor + ".\n");
						}
						else {
							instructions.add(" " + (i+1) + ". Go up the stairs to floor " + destFloor + ".\n");
						}
					}
					else {
						if (curFloor > destFloor) {
							instructions.add(" " + (i+1) + ". Take the elevator down to floor " + destFloor + ".\n");
						}
						else {
							instructions.add(" " + (i+1) + ". Take the elevator up to floor " + destFloor + ".\n");
						}
					}
				} 
				else {
					if((route.get(i-1).getType() == 1 || route.get(i-1).getType() == 7) && (route.get(i).getType() == 1 || route.get(i).getType() == 7)) {
						instructions.add(" " + (i+1) + ". Progress from " + route.get(i).getName() + " to " + route.get(i+1).getName() + ".\n");
					}
					else {
						// if previous move more of a horizontal change then
						if(Math.pow(route.get(i).getPosition().getX() - route.get(i-1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i-1).getPosition().getY(), 2)) {
							// if previous move was to the left then
							if(route.get(i).getPosition().getX() - route.get(i-1).getPosition().getX() < 0) {
								// if next move more of a horizontal change then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move back to the right
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself from " + route.get(i).getName() + " and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move also to the left
									else {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + "  towards " + route.get(i+1).getName() + ".\n");
									}
								}
								// else if next move more of a vertical change then
								else {
									// if next move down
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// else if next move up
									else {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
							}
							// else if previous move was to the right then
							else {
								// if next move is more horizontal than vertical then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move is also to the right then
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + " towards " + route.get(i+1).getName() + ".\n");
									}
									// if next move is to the left
									else {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself from " + route.get(i).getName() + " and go to " + route.get(i+1).getName() + ".\n");
									}
								}
								// if next move is more vertical than horizontal then
								else {
									// if next move is down
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is up
									else {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
							}
						}
						// else if last move was more vertical than horizontal then 
						else {
							// if last move was up then
							if(route.get(i).getPosition().getY() - route.get(i-1).getPosition().getY() < 0) {
								// if next move is more horizontal than vertical then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move is to the right then
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is to the left then
									else {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
								// if next move is more vertical than horizontal then
								else {
									// if next move is down then
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is up
									else {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + " towards " + route.get(i+1).getName() + ".\n");
									}
								}
							}
							// if last move was down then
							else {
								// if next move is more horizontal than vertical then
								if(Math.pow(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX(), 2) > Math.pow(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY(), 2)) {
									// if next move is to the right then
									if(route.get(i).getPosition().getX() - route.get(i+1).getPosition().getX() < 0) {
										// turn left
										instructions.add(" " + (i+1) + ". Turn left at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
									// if next move is to the left then
									else {
										// turn right
										instructions.add(" " + (i+1) + ". Turn right at " + route.get(i).getName() + " and go to " + route.get(i+1).getName() + ".\n");
									}
								}
								// if next move is more vertical than horizontal then
								else {
									// if next move is down then
									if(route.get(i).getPosition().getY() - route.get(i+1).getPosition().getY() < 0) {
										// keep going
										instructions.add(" " + (i+1) + ". Keep going along the corridor from " + route.get(i).getName() + " towards " + route.get(i+1).getName() + ".\n");
									}
									// if next move is up
									else {
										// turn back (shouldn't ever get used, no path will involve dead end)
										instructions.add(" " + (i+1) + ". Turn back on yourself at " + route.get(i).getName() + "  and go to " + route.get(i+1).getName() + ".\n");
									}
								}
							}
						}
					}
				}
			}
		}
		return instructions;
	}

	private void displayResult(List<String> route) {

		for(int i = 0; i < route.size(); i++) {
			path = path.trim() + route.get(i);
		}

	}

	private void resetDisplay() {
		this.loc.setText("");
		this.dest.setText("");
	}

	private void resetPath() {
		this.path = "    ";
	}

	private void resetStates() {
		this.root = " ";
		this.open.clear();
		this.closed.clear();
		this.instructions.clear();
		this.current = null;
		for(int k = 0; k < complete.size(); k++) {
			this.complete.get(k).setParent(null);
		}
		this.targetFound = false;
		this.startFound = false;
		this.neighbourFound = false;
	}

	public static void main(String[] args) {
		Search find = new Search();

		//createGUI();
		find.createGUI();
	}

}